2008/01/30

ロカポーター誕生の記録(7)

7.(データ途中)可変精度のアイデア

ロカポータの一番前面に出したい特徴として、精度の途中可変能力がある。
仕組みは追々説明させていただくが、これによって、いろいろな精度のデータを混在させることが可能になる。これは他の圧縮技術ではあまり見かけないが、どうでしょうか?

一番に思いつくのは、マップマッチング技術(NI-Lab. さんのサイトより)との相性。マップマッチング技術を使えば、経路情報に多少の誤差があっても、ぴったり道路に合わせて修正することが出来る。それを見越して経路情報はかなり荒い精度に落とし、情報量を減らすことができる。

同時に、出発地点、目的地、経由地点(お店)などはピンポイント情報にすることにより、精度を損なわずにデータを混ぜることができる。

たとえば、高速と一般道が平行している道路で、どちらか判別がつき難い程度に情報量を落としても、料金所の場所を経由地点としてピンポイントで表すことで、高速を利用することが表現できる。ロカポーターでは、エンコードした際にどの精度でエンコードしたかの情報も保存できるので、あとから「このデータは精度が粗いから重要度は低い」「経路の中でここだけピンポイント精度にしてあるのは、重要な場所である」というように、解釈することが可能です。

海外旅行の経路+立ち寄ったお店、写真をとった場所、あの公園のあの銅像!などにも使えます。

保存精度を選ぶことで、データを削って効率を稼ぐ(ある意味、非可逆圧縮)ことと、本当に精度を保ちたい場所(可逆圧縮)を自由に混在させることができる。


実は、この可変精度(というか混在精度)のアイデアを思いついたのは、年が明けてから。白状してしまうと、ジオメディア2008新年会ライトニング・トークをさせてもらうことになり、プレゼンの原稿を考えないと、、、と思っている時に急に思いついたものです。正月休みも一部返上で働いていた帰宅中の電車の中でした。

それまで、実は軽量アルゴリズムの「ロカポ圧縮Light版(現ロカポーター)」と、いろんな情報圧縮理論を組み合わせて圧縮効率を追求する「ロカポ圧縮Max版」の二本立てでいこうと思っていました。プレゼンも二本を紹介する内容でした。
でもこの可変精度ができることで、Light版の地位がいきなりアップ!。
さらに、これによって「サービス間連携ツール」としての利便性が格段にアップすることに気づく。

逆にMax版は可変精度が出来ないので、圧縮技術としては良いかもしれないが、サービス関連携にはあまりメリットがすくなさそうになり、開発を中止することにしました。それに、単なる圧縮効率の追求だけなら、頭のいい人がちょっと考えればすぐによりよい物が作れると思いますし。というわけで、可変精度で必要なところだけ可逆圧縮、どうでもいいところは非可逆圧縮にできる Light版一本でのデビュー決定!プレゼンも作り直し!

これがジオメディア2008新年会のお披露目発表の前夜23時ごろ。そのまま徹夜でやっつけのプレゼンを作って、東京へ移動!なんと余裕のないスケジュール!

ライトニング・トークの後、ずっとロカポ圧縮の相談にのっていただいていたここギコ!さんから「可変精度のことは初めて聞きました!」と驚かれましたが、それもそのはず。思いついてからほんの数日しか経ってないのですから。。。。

実際の利用場面においては、そこそこの経路情報でも結構な大きさのテキストデータになってしまうと思います。しかし、この可変精度の特性と、マップマッチングを前提にしたデータ量の間引きの組み合わせによって、ロカポーターは位置情報ポータビリティーの現実的な手段になると確信しています。

続く。

ロカポーター誕生の記録(6)

6.位置情報のポータビリティー

ヒアリングで出てきた「他社と連携する」「経路(エリア)丸ごと渡す」という二点。
このジャンルならロカポ圧縮を活かせる。いや、活かせるどころか、

業界のパラダイムを180度変えてしまう可能性がある!


とおもいました。これは、単なる圧縮ツールじゃない。LBS/GISサービス間の複雑な連携を可能にするプラットフォームなんだ!

今まではワンストップサービスの大手地図サービスサイトがユーザーを引きつけていました。それは自社内でしかデータの流用が効かなかったので、必然的に総合サービスを提供できるのは体力のある巨人だけでした。でもITの流れをみてみると、ワンストップサービスのAll-In-Onポータルがもてはやされた時代は過ぎ、いまや特化戦略が必須です。

位置ベース・サービスでも各機能に特化した位置情報ベンチャー同士が有機的に連携して、総合的なサービスを作る。あるいは、各ベンチャーを部品として、アマチュアが複雑なマッシュアップを作る。そのためには、複雑な位置情報を簡単に流通させるプラットフォームが必要だ。

いわば、サイトで扱う情報・扱った情報の『位置情報のポータビリティー』。

つまり、業者やサービスを問わず自由に位置情報データを流通できるかどうか。
ロカポーターなら単なるテキスト。十分通用する。

これで特化型位置情報ベンチャーの時代が来る。ベンチャーは連携と前提に最小限のリソースでビジネスを立ち上げることができる。All-In-Oneの巨人の時代は廃れていく。少し前、IT業界に起こったパラダイムシフトが、LBS/GIS業界にも起ころうとしている。これでカーナビ+αからなかなか抜け出せなかったLBS/GIS業界に革命を起こすよう位置情報ベンチャーが出てくるきっかけになるかもしれない。

その起爆剤というか、触媒というか、そういう部分に貢献できると思うと、なんだかとてもうれしい。
これまで『位置情報ロカポ』の普及活動をやってきたが、社会に対して、今すぐ貢献できるのはロカポよりもロカポーターかもしれない。そんな気がしています。


ところで、2/4現在、ロカポータ発売開始予定が準備が遅れており、2/8に延期させて頂きました。大変ご迷惑をおかけしております。

ロカポーターの実際のアルゴリズムについてもこのブログで徐々にご紹介させて頂きますが、次回は2/8とさせていただきます。

ロカポーター誕生の記録(5)

5. 使い道は???ヒアリング道中記

2007/10/11にアルプスラボさんに伺って、ロカポ圧縮について相談させて頂きました。
それで、それまでロカポ圧縮が実際のところ役に立つのかどうか、疑問に思っていた大きな点を改めて再認識。それは

「データベースにさえアクセスできれば、キー情報だけ持っていればいいので、圧縮する必要はない」

という点。
QRコードにしてもキー情報だけ掲載していればよいので、そこに経路情報がそのまま載っているメリットは、パケット代節約とか、通信速向上程度にしかならず、本質的なメリットではない。
だから、圧縮が役に立つのは、電波の入らない地下街(今時そんなところあるのか?)とか、登山中の山奥とか。

2007/10/12にリクルート・メディアテクノロジー・ラボを訪問。フナミタカオさんにお会いして、ロカポ圧縮の利用アイデアを聞いていただいた。
その中に「経路検索サイトなどで検索した結果を、そのままホットペッパーに持ってきて、経路沿いのレストランのみを検索する」みたいなアイデアがあったのですが、これに対してフナミさんが仰るには「物理的にデータベースにアクセスできる環境でも、他社のデータベースはアクセスできないのと同じ。企業をまたがった連携には有効ではないか」というコメントを頂いた。
さすがフナミタカオさん!
このコメントが以後ずっと頭の中に残っていました。(あとで考えると、これがアイデアの起爆剤となりました。フナミさん、どうもありがとう!)

2007/12/12
フリーマップレット「マップサーファー」の件で、大手地図系システム会社さんを訪問。
余談時間にロカポ圧縮を紹介。「経路情報をそのまま渡せる」といった時に技術の方が「それならあれもできる、あれもできる、、、」といろいろ考えておられる様子。これまでLBSサービスでは「経路をまるごと渡す」という選択肢は少なかったのかもしれない。
それが「もし経路ごと渡すことが可能ならば、、、」というお題目があれば、技術者のクリエイティビティを刺激するのでしょう。


この「他社と連携する」「経路(エリア)丸ごと渡す」という二点を、ずっとずっと頭に引っかかっていました。年末にいろいろな仕事が重なり、ものすごくハードだったのですが、そのフラフラの頭のときに突然ひらめきました!

6.に続く

ロカポーター誕生の記録(4)

4.既存の圧縮技術

ここで、先行事例で見つけた面白いもの、を紹介します。
松下電器産業の足立 晋哉さんというITS分野らしい(?)方の発明。

(特許公開2007-104543『緯度経度データ列の圧縮装置及び圧縮方法』
※私の説明はアバウトなので、詳しくは特許電子図書館でこの文献を見てください)

基本的には道路を記述する方法です。

同じように基点と差分を記録していく方式なのだが、通常は
「緯度の変化量」
「経度の変化量」
とするところを

「移動距離は道路上で等距離となる点に振りなおして」
「角度の変化量の変化量」
と一種のベクトルに変換したデータで経路というか道路を記録する。
でなにか凄いかというと、まず移動距離は等距離で一定なので省略できる。これで1次元分のデータ省略(すごーーーい!)
で、もっとすごいのが「角度の変化量の変化量」のところ。
正確には角度の変化量の予測値と実測地の差分だそうですが。
簡単にいうと、一定のRのカーブを曲がっている時は、各点間を結ぶ線がなす角度は常に一定となるので、次の予測値と実測値の差はほとんどゼロとなる。
さらに、右左折した場合、差分はほぼ90度となる。
経路に一定曲率の道路(直線を含む)と90度の交差点が多いばあい、経路をトータルすると、差分データの分布は0度と90度の周りにかなり集中すると考えられる。これだけデータの偏りがあれば、ホフマン符号などその他の情報圧縮でかなり圧縮できる。

この人天才だなあ。。。一度お会いしたいです。
12月にITSの学会でこの人の発表があったのですが、予定があっていけなかった。残念!

ロカポーター誕生の記録(3)

3.試行錯誤と勉強のやり直し!

その後、どうせ圧縮するなら敢えてロカポを使う必要もないし、いろいろなフォーマットの位置情報コードを作って、それぞれで圧縮効果とか、可逆性が保障されているかを検討しながら試行錯誤することにしました。

同時に、本格的な情報圧縮技術について、昔やった記憶があいまいなので再度勉強開始。ホフマン符号化、LZ法、ランレングス法など。難しいな あ。。。考えた人凄ーい、と思いながら、エクセルベースで簡単なプログラムを組みつつ、いろんな経路情報を実際に符号化して、どれくらい圧縮できるかテス ト。こちらはアルゴリズムが複雑怪奇でもいいから、とにかく圧縮効率だけを追及する「ロカポ圧縮MAX」として別バージョンで出すつもりでした。

経路や領域の情報は、隣り合う点同士は値の変化が少ないので、データ同士の差分を取る方式やMPEG(画像の中の動く部分だけを検出して保存)みたいな方法が向いている。でも一般の情報圧縮は主にFAX画像や音声や映像、テキスト文書をターゲットに開発された歴史もあるので、なんとか経路や領域という地理情報特有の特徴をうまく利用した圧縮アルゴリズムができないか、いろいろ考えました。

たとえば、都道府県とか、マピオンの国獲りみたいな、ある面を複数の領域を分割したデータでは、県境などの境界にあたる部分は二つの領域で共有されている。一辺が接している二つの正方形を思い浮べて頂くとわかりやすいが、この場合接している辺の情報は、二つの正方形領域の情報にそれぞれ含まれている。両方の正方形を、4つの辺の集まりとしてバラすと、共有している辺は順番の正逆はあるかもしれないが、符号以外は同じデータ列なので、これを利用して圧縮できないか、など。
このアイデアはまだLocaPorterでは実現できていないが、領域分割のデータを圧縮するにはとても効果的かなと思っている。(ここで発表してしまったので、特許にはできないですが。笑)

こんな感じで、いろいろ考えたというよりは、エクセルでマクロとVBAでプロトタイプを作っては比較するということを繰り返しました。

4.に続く

ロカポーター誕生の記録(2)

2.「doodle」でおなじみのゴーガさんとの雑談にて

2007年8月31日、ゴーガさんから「位置情報を利用するサイト間で取得したGPS情報を共有する」GISゲートウェイの企画を聞き、『これはすばらしい!』と渋谷にあるゴーガさんに飛んでいきました。以前から各社URLの緯度経度のフォーマット(ついでに測地系も!)に全く統一性がなく、連携しようにもいちいちフォーマット変換する必要がありました。私も以前からnavitoGatewayというフリーウェアやマップサーファーというガジェットを作ったりしていて、位置情報の流通という事に非常に関心があったので、二つ返事で参加させていただきました。

ロカポはコンテンツ商売ではないのと、私が元々携帯サイト系の技術が苦手なのもあって、これまで携帯サイトにはあまり関わっていませんでした。

その話の中の雑談で、ゴーガさんから携帯電話のブラウザではURLの文字数制限が厳しいものがあると聞きました。1点の位置情報なら問題ないが、4点、5点と増えてくると厳しくなってくるという話でした。

私はロカポ開発時に情報量と表示桁数の関係といろいろ調べたことがあったのですが、1メートル前後の精度で場所を表すには、緯度経度あわせて15文字の数字が必要です。小数点や区切り文字を考えると一箇所に付き約20文字。元のサイトアドレスなどで20文字使うとすると、4箇所の情報であっという間に100文字を超えます。

そんな話をしていて、「ロカポDIYマップ」というサービスで経路情報の圧縮をしていたので、その技術がありますよ、という話をしていました。

家に帰って、改めてロカポDIYマップの圧縮仕様 (現在のロカポ仕様Ver2.0では削除)を見直していて、ふと、さらに圧縮できるアイデアを思いつきました。

その時点での名前は「ロカポ圧縮」。なんとベタな名前(苦笑)

2007/9/22にリクルートでマッシュアップ・アワード応募者のパーティがあり、ここギコ!さんにロカポ圧縮のアイデアのお披露目、というか相談にのってもらいました。

3へつづく

ロカポーター誕生の記録(1)

位置情報圧縮技術(LocaPorter)発表後の各方面より多数のお問合せを頂きました。どうもありがとうございました。現在ドキュメント整備など、販売の準備を進めておりますので、もうしばらくお待ち下さいませ。

それまでに順次、LocaPorter開発の歴史を記録に残しておこうと思います。

1.ロカポDIYマップ時代
2006年1月にロカポDIYマップという、グーグルマップにマーカーや線を引いて、それぞブログに貼り付けられるサービスを始めました。(今やこんな機能はどこのサイトにもありますよね)
その当時はまだ数社しかそういったサービスをしていませんでした。他社さんは、(推測ですが)ユーザが作った経路情報をデータベースに入れて、キーとなる文字列のみをURL化する方式だったのですが、ロカポでは借りているサーバーの容量が小さかったので、ユーザーさんが増えた場合、すぐに対応できなくなってしまう心配がありました。結果、ユーザーさんのデータはユーザーさんに持ってもらおう、という他力本願の思考回路となりました(笑)。
でもユーザーさんに渡せるのはURLのみ。URLに経路情報を入れるには長すぎるし、、と考えていたとき、
「そうかロカポのフォーマットの左右非対称性を活かせば簡単に可逆圧縮できるぞ」
、、、ということでロカポをベースにした経路圧縮を作りました。

もう少し説明すると、ロカポは「文字、文字、数字」のパターンなので、「省略するのは左側のみか、右側のみのどちらか」という制限さえ設ければ
「文字、文字」---数字が省略されている(精度を荒くしている)
「文字、数字」---左の文字が省略されている(上位桁の省略)
「文字」-----右側の文字と数字が省略されている(精度を荒くしている)
「数字」-----左側の文字+数字が省略されている(上位桁の省略)
ということが明確です。
で、ロカポはエリアコードの上位桁と、詳細情報のローカルコード下位桁に分かれているので、
エリアコードは同じことが多いので、同じ部分は省略(上位桁の省略・左側のみ)
ローカルコードは、多少精度を粗くしてもナビ用には問題ないので右側のみ省略
というようにすれば、かなり文字数を減らせる、という原理です。

これはロカポの仕様Version 1.0 には書いていたのですが、まずは素のロカポを知ってもらう上で返って邪魔となるので、現在の仕様 version 2.0では消された、いわば幻の仕様です。 (その他、余談ですが、ロカポVersion 1.0 には圧縮仕様の他に、経路情報、領域情報、点のグループ、を表す仕様がありました。)

その後2年間そのままにされていましたが、このときの幻の仕様がロカポーターの卵となりました。

2へ続く。

2008/01/23

訂正!

hatenaブックマークで指摘いただきました(ご指摘感謝!)
「「精度1mで情報を取るのと、精度10mで情報を取るのでは、元の精度を再現するのに必要な情報量は当たり前ですが10倍になります。」→ダウト! :-)
そのとおりです!すみません。
情報量という意味ではlog2(10) ≒3.3219倍です。(logの底は2)

で、表示上何桁必要かは、何進法を使うかで変わります。10進法なら一桁増えるだけなので、今N桁で表示しているところを、N+1桁必要となるので、表示上必要な桁数の増加は (N+1)/N 倍です。

適当なセールストークになってしまいまして、申し訳ございません(反省)。

2008/01/21

経路やエリア情報の圧縮技術を開発、特許出願しました。LocaParam改めLocaPorter。

先のジオメディア2008新年会発表していたのですが、昨年9月から、
・経路
・領域
・複数地点
など、緯度経度の複数セット情報を短いテキストに圧縮する圧縮技術を開発し、先週特許出願いたしました。(プレスリリース

元々は、URL文字数制限の厳しい携帯サイト用のURLに、何点もの緯度経度を入れたい、という話を聞き、ロカポDIYマップで使っているURL圧縮仕様(今は亡きロカポ仕様Ver1.0の圧縮拡張フォーマット)をベースにスタート、ああすればもっと短くなるのでは?、こうすればどうだ?などいろいろ試行錯誤していました。一方、情報圧縮理論もちゃんと勉強してバイナリレベルで究極に圧縮できればどのくらいまで小さくなるだろう?など。結構おもしろかったです。

サイズだけを追求すれば
1.緯度経度を整数にする
2.差分をとってバイナリで表す
3.ワイル符号化、γ符号化、σ符号化などの手法で2進数にする
4.ホフマン符号化、LZ法などで情報圧縮
とやれば小さくなります。

でももっと使い勝手と、携帯やPDAのCPUでも軽~く圧縮・解凍できて、しかも実装も簡単なのが望ましい。ということで、試行錯誤の上にできたのが、今回の圧縮技術です。

これまでは、経路やエリアなどを扱うにはデータベースやKMLファイルを使うことがほとんどだったと思います。この圧縮技術では位置情報をテキスト文字列に圧縮します。
QRコード、RF-ID(ICカード)、URL文字列、低速パケット通信回線、赤外線通信など、文字数や容量の制約が厳しい媒体でどんどん使ってください。

URLに使っても%XXとURLエンコードされてしまうと、せっかくの1文字が3文字になるケースがあります。そうならないよう、URLエンコード対象外の64文字のみで圧縮データは表現されます。それに64という数字はあとからバイナリにしてさらに圧縮、、、とかやりたくなったときでも無駄なビットロスがないですし。

位置情報圧縮技術の主な特徴です。
①軽量な圧縮アルゴリズムですが、ホフマン符号等を駆使した場合の約60%くらいの能力はあります。サンプルの経路データでテストした結果です。
 ・5箇所の緯度経度 →約22%に圧縮
 ・60箇所の緯度経度 →約13%に圧縮
 ・1200箇所の緯度、経度、高度 →約8%に圧縮
  (弊社実験結果より。データの内容により圧縮率は異なる)
②オン・ザ・フライ処理
符号化、復号化とも先頭から順にデータを追加していく方式なので、測位しながら記録し、さらに途中で電源が切れるようなケースでも、すでにあるデータにどんどん追加可能です。
③精度の違うデータの混在が可能
これが目玉です!最後までバイナリレベルのサイズ優先と、バランス優先の二本立てにしようかどうか迷っていたのですが、このメリットが無いことでサイズ優先の選択肢が消えました。

同じ経路でも、精度1mで情報を取るのと、精度10mで情報を取るのでは、元の精度を再現するのに必要な情報量は当たり前ですが10倍になります。
仮に海外旅行の旅行記をとるとして、飛行機の飛行経路は一応残したい、立ち寄ったお店の情報はピンポイントの精度が欲しい、となると「広範囲×高精度」でデータ容量はとても多くなってしまいます。元データそのものが大きいので、いくら圧縮しても限界があります。だから通常、このような場合は精度のことなる別々のデータとして、それぞれ圧縮することになります。

この圧縮技術では、一つの経路やエリア情報の中で、精度の異なるデータの混在が可能です。さらに、復号する際に、圧縮時の精度情報も取得できます。
カーナビなどではマップマッチングの技術があり、経路情報はある程度ルートを外れても道路上に戻してくれます。これを利用して、マップマッチングを前提に、ルート情報はかなり情報量を落として容量を節約しつつ、出発地、経由するお店、目的地は1mのピンポイント精度で表現する、ということが可能です。


圧縮の効果単独で、たとえばパケット量を減らしてレスポンスを上げるとか、そういう用途にどんどん使って頂きたいのですが、それよりも位置情報サービス同士の連携に使って欲しいと考えています。

そもそも
現在地→周辺情報
が1:Nなのに対して
現在経路→経路沿い情報
では N:Nになるので、通常の
GET/POSTで送信→XML/JSONで受信 のよう単純なデータの流れは難しい。

例えばルート検索後、ルートに沿ったレストランを検索したい場合、ルート情報がデータベースに入っている限り、通常他社サービスからのアクセスはできません。必然的に、こういった複合サービスを提供したい場合は、ワンストップサービスとなり、一つのサイトでルート検索も、路線検索も、ホテル検索も、レストラン検索も、、、ということになりがちです。

でも一般のITの世界では、All in one のポータルサイトより、各ジャンルに特化したサイト同士がマッシュアップする時代です。百貨店より専門店です。位置情報系のサービスだけが百貨店戦略を続けるのは難しい。
そこで、検索した経路や、地図上にマウスで描いたエリアなど、この圧縮技術で一つの文字列にパラメータ化できます。そうして位置情報系サイト同士のマッシュアップが簡単にできるようになれば、どんな斬新なサービスが出てくるのか想像もできません。なぜなら、今の現状ではただ一箇所だけの情報(現在地とか地図の中心とか)でさえ、サービス間連携している例は少ないからです。

だからこのサービスを圧縮ではなく、連携を前面に打ち出して「LocaPorter」という名称にしました。
ジオメディア2008では「LocaParam」という名前で発表していましたが、パラメータというより、各サービスで使った位置情報を他のサービスへ自由に「持ち運ぶ入れ物」というコンセプトがぴったりで、こちらにしました。それにLocaPointの名付け親のネーミング・コンサルタントからLocaParamは英語的ではちょと、というアドバイスをもらい、LocaPorterはOKもらったのと、別の方から「ロカポ」という音が入ってた方がいいという意見も頂いたので。

この位置情報圧縮技術、1月末か2月始めまでにドキュメントなどを整備して、ライセンス販売と導入支援を開始する予定です。

技術の詳細な内容は当面はNDA前提の公開となりますが、ロカポと同じように、近いうちにオープンにしたいと考えています。

LocaPorterをどうぞよろしくお願いいたします。